/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MyCalendarI {

	class Node {
		public Node(int start, int end) {
			l = start;
			r = end;
		}

		int l, r;
		Node left, right;
	}

	Node root = null;

	public boolean book(int start, int end) {
		if (root == null) {
			root = new Node(start, end);
		} else {
			Node cur = root;
			Node pre = null;
			boolean leftTag = false;
			while (cur != null) {
				pre = cur;
				if (end <= cur.l) {
					leftTag = true;
					cur = cur.left;
				} else if (start >= cur.r) {
					leftTag = false;
					cur = cur.right;
				} else {// 有重叠
					return false;
				}
			}
			if (leftTag) {
				pre.left = new Node(start, end);
			} else {
				pre.right = new Node(start, end);
			}
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyCalendarI myCalendarI = new MyCalendarI();
		System.out.println(myCalendarI.book(10, 20));
		System.out.println(myCalendarI.book(15, 25));
		System.out.println(myCalendarI.book(20, 30));
	}

}
